/* 中序遍历线索二叉树 */

#include <iostream>
#include "InThreadBiTreefun.h"
using namespace std;

// 找到二叉树p在中序遍历时的第一个结点
TNode *First(TNode *p)
{
  // 不断寻找左孩子结点
  while (p->ltag == 0)
    p = p->lchild;
  return p;
}

// 找到p结点的下一个要遍历的结点
TNode *Next(TNode *p)
{
  // 如果指向的是右孩子
  if (p->rtag == 0)
    return First(p->rchild);
  
  // 如果指向的是后序结点
  else
    return p->rchild;
}

// 中序遍历
void In(TNode *p)
{
  // 找到第一个要访问的结点
  TNode *q = First(p);
  
  // 遍历
  for (; q != NULL; q = Next(q))
    cout << q->data << " ";
}

int main()
{
  // 创建中序线索二叉树
  TNode *T = create_iTree();
  TNode *pre = NULL;
  
  // 二叉树不为空
  if (T != NULL)
  {
    // 建立线索
    InTh(T, pre);
    
    // 处理最后一个结点
    pre->rchild = NULL;
    pre->rtag = 1;
  }
  
  // 中序遍历
  In(T);
}